RootishArrayStack: A Space-Efficient Array Stack
Discover the need of RootishArrayStack.
We'll cover the following
The data structures that store their data in one or two arrays and avoid resizing these arrays too often, the arrays frequently are not very full. For example, immediately after a resize() operation on an ArrayStack, the backing array is only half full. Even worse, there are times when only one-third of it contains data.
Visual demonstration#
A sequence of add(i, x) and remove(i) operations on a RootishArrayStack is illustrated below. Arrows denote elements being copied.
1 of 5
2 of 5
3 of 5
4 of 5
5 of 5
In this lesson, we discuss the RootishArrayStack data structure, that addresses the problem of wasted space. The RootishArrayStack stores elements using arrays. In these arrays, at most array locations are unused at any time. All remaining array locations are used to store data. Therefore, these data structures waste at most space when storing elements.
A RootishArrayStack stores its elements in a list of arrays called blocks that are numbered . See the above slides. Block contains elements. Therefore, all blocks contain a total of
elements. The above formula can be obtained as shown in the following illustration:
In the illustration above, the number of shaded squares is the same. Together the white and shaded squares make a rectangle consisting of squares.
As we might expect, the elements of the list are laid out in order within the blocks. The list element with index is stored in block , elements with list indices and are stored in block , elements with list indices , , and are stored in block , and so on. The main problem we have to address is that of determining, given an index , which block contains as well as the index corresponding to within that block.
Determining the index of within its block turns out to be easy. If index is in block , then the number of elements in blocks is . Therefore, is stored at location
within block . Somewhat more challenging is the problem of determining the value of . The number of elements that have indices less than or equal to is . On the other hand, the number of elements in blocks is . Therefore, is the smallest integer such that
We can rewrite this equation as
The corresponding quadratic equation has two solutions: and . The second solution makes no sense in our application since it always gives a negative value. Therefore, we obtain the solution . In general, this solution is not an integer, but going back to our inequality, we want the smallest integer such that . This is simply
The RootishArrayStack operations#
With this out of the way, the get(i) and set(i, x) methods are straightforward. We first compute the appropriate block and the appropriate index within the block and then perform the appropriate operation:
If we use any of the array-based data structures for representing the blocks list, then get(i) and set(i, x) will each run in constant time.
The add(i, x) method will, by now, look familiar. We first check to see if our data structure is full, by checking if the number of blocks, , is such that . If so, we call grow() to add another block. With this done, we shift elements with indices to the right by one position to make room for the new element with index :
The grow() method does what we expect. It adds a new block:
Ignoring the cost of the grow() operation, the cost of an add(i, x) operation is dominated by the cost of shifting and is therefore , just like an ArrayStack.
The remove(i) operation is similar to add(i, x). It shifts the elements with indices left by one position and then, if there is more than one empty block, it calls the shrink() method to remove all but one of the unused blocks:
The implementation of the shrink() method is:
Once again, ignoring the cost of the shrink() operation, the cost of a remove(i) operation is dominated by the cost of shifting and is therefore
Explanation
Let’s start our explanation from the start of main() in main.py file.
- Line 67: It creates a new instance of the
RootishArrayStackclass with the type of the elements to be stored in the stack beingInteger. The new instance is assigned to the variablestack. - Lines 69–71: It adds the elements
1,2, and3to the stack at indices0,1, and2, respectively. - Line 72: It prints the elements of
stack. - Line 74: It removes an element from
stackfrom index1using theremove()method. - Lines 77–78: It adds the elements
2and4tostackat indices1and3, respectively. - Line 81: It clears all the elements from
stack.
DualArrayDeque: Building a Deque from Two Stacks
Analysis of RootishArrayStack